package leetcode.dp;

import java.util.ArrayList;
import java.util.List;

public class Test139 {
    public static void main(String[] args) {
//        String a = "abc";
//        String substring = a.substring(-3, 3);
//        System.out.println(substring);
        List<String> list = new ArrayList<>();
        list.add("aaa");
        boolean leetcode = wordBreak("aaaa", list);
        System.out.println(leetcode);
    }
//    输入: s = "leetcode", wordDict = ["leet", "code"]
//    输出: true
//    解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/word-break
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static boolean wordBreak(String s, List<String> wordDict) {
//        dp[0] = true
        //dp[j] = dp[j] && Dict.contains(s.subStr(length,j))
        boolean[] d = new boolean[s.length()+1];
        d[0] = true;
//        for (int i =0;i<d.length;i++){
//            d[i] = true;
//        }
            for (int j=1;j<=s.length();j++){
                for (int i =0;i<wordDict.size();i++){
                int length = wordDict.get(i).length();
                if (j<length){
                    continue;
                }
                d[j] = d[j-length] && wordDict.contains(s.substring(j- length,j));
                if (d[j]){
                    break;
                }
            }
            if (d[s.length()]){
                return true;
            }
        }
        return false;
    }
}
